__author__ = 'st316'
'''
Given a string S and a string T, find the minimum window in S which will contain all the characters in T
in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
'''

import collections


class Solution:
    # @return a string
    def minWindow(self, S, T):
        if not S or len(S) < len(T):
            return ''
        ts = {}
        for c in T:
            if c in ts:
                ts[c] += 1
            else:
                ts[c] = 1
        s = {}
        q = collections.deque()
        se = 0, -1  # result: start,end
        rl = len(S)  # substring len, default len(S)
        count = 0 # replace the contains method
        for i in xrange(len(S)):
            if S[i] in T:
                q.append((S[i], i))
                if S[i] in s:
                    s[S[i]] += 1
                else:
                    s[S[i]] = 1
                if s[S[i]] <= ts[S[i]]:
                    count += 1

                #while self.contains(s, ts):  # find a substring
                while count == len(T):  # find a substring
                    t = q[-1][1] - q[0][1] + 1
                    se, rl = (se, rl) if rl < t else ((q[0][1], q[-1][1]), t)
                    c = q.popleft()[0]
                    s[c] -= 1
                    if s[c] < ts[c]:
                        count -= 1
                    if s[c] == 0:
                        s.pop(c)

        return S[se[0]:se[1] + 1]

    def contains(self, A, B):
        if len(A) != len(B):
            return False
        for i in A:
            if A[i] < B[i]:
                return False
        return True

    # @return a string
    def minWindowX(self, S, T):
        sLen = len(S)
        tLen = len(T)
        needToFind = {}
        hasFound = {}

        for c in T:
            if c in needToFind:
                needToFind[c] += 1
            else:
                needToFind[c] = 1
            if c in hasFound:
                pass
            else:
                hasFound[c] = 0

        minWindowLen = sLen + 1
        minWindowBegin = 0
        minWindowEnd = -1

        count = 0
        begin = 0

        for end in xrange(sLen):
            # skip characters not in T
            if S[end] not in needToFind:
                continue
            hasFound[S[end]] += 1
            if hasFound[S[end]] <= needToFind[S[end]]:
                count += 1

            # if window constraint is satisfied
            if count == tLen:
                # advance begin index as far right as possible,
                # stop when advancing breaks window constraint.
                while needToFind.setdefault(S[begin], 0) == 0 or \
                                hasFound.setdefault(S[begin], 0) > needToFind.setdefault(S[begin], 0):
                    if hasFound.setdefault(S[begin], 0) > needToFind.setdefault(S[begin], 0):
                        hasFound[S[begin]] -= 1
                    begin += 1

                # update minWindow if a minimum length is met
                windowLen = end - begin + 1
                if windowLen < minWindowLen:
                    minWindowBegin = begin
                    minWindowEnd = end
                    minWindowLen = windowLen

        #return True if (count == tLen) else False
        return S[minWindowBegin:minWindowEnd + 1]


if __name__ == '__main__':
    s = Solution()
    print s.minWindow('acbbaca', 'aba')